package org.cabbage.lintcode;

/**
 * 假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。
 * <p>
 * 你可以假设数组中不存在重复的元素。
 *
 * @author gezhangyuan
 */
public class Search {

    private int index = -1;

    public static void main(String[] args) {
        Search search = new Search();
        System.out.println(search.search(new int[]{6, 8, 9, 1, 3, 5}, 5));
    }

    public int search(int[] A, int target) {
        if (A.length == 0) {
            return -1;
        }
        searchBinch(A, target, 0, A.length - 1);
        return index;
    }

    private void searchBinch(int[] A, int target, int begin, int end) {
        int t = (begin + end) / 2;
        int temp = A[t];
        if (temp == target) {
            index = t;
            return;
        }
        if (begin == end) {
            return;
        }
        if (target > temp && target <= A[end]) {
            searchBinch(A, target, t + 1, end);
            return;
        }
        if (target < temp && target >= A[begin]) {
            searchBinch(A, target, begin, t - 1);
            return;
        }
        if (Math.abs(temp - A[begin]) > Math.abs(A[end] - temp)) {
            searchBinch(A, target, begin, t - 1);
        } else if (Math.abs(temp - A[begin]) < Math.abs(A[end] - temp)) {
            searchBinch(A, target, t + 1, end);
        }
    }
}
